package 链表;

import java.util.Stack;

public class BM9_删除链表的倒数第n个节点 {

	public static void main(String[] args) {
		ListNode node5 = new ListNode(5);
		ListNode node4 = new ListNode(4);
		ListNode node3 = new ListNode(3);
		ListNode node2 = new ListNode(2);
		ListNode node1 = new ListNode(1);
		node1.next = node2;
//		node2.next = node3;
//		node3.next = node4;
//		node4.next = node5;
		BM9_删除链表的倒数第n个节点 test = new BM9_删除链表的倒数第n个节点();
		test.removeNthFromEnd(node1, 2);
	}

	public ListNode removeNthFromEnd (ListNode head, int n) {
		ListNode preHead = new ListNode(-1);
		preHead.next = head;
		ListNode curr = preHead;
        Stack<ListNode> stack = new Stack<>();
        
        while(curr != null) {
        	stack.push(curr);
        	curr = curr.next;
        }
        
        for(int i=0;i<n;i++) {
        	stack.pop();
        }
        
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        return preHead.next;
    }
	
	public ListNode removeNthFromEnd01 (ListNode head, int n) {
		ListNode preHead = new ListNode(-1);
		preHead.next = head;
		ListNode first = head;
		ListNode second = preHead;
		for(int i=0;i<n;i++) {
			first = first.next;
		}
		while(first != null) {
			first = first.next;
			second = second.next;
		}
		second.next = second.next.next;
		return preHead.next;
	}
}
